package targetToOffer.firstDay;

import java.util.Deque;
import java.util.LinkedList;

public class minStack {
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		MinStack minStack = new MinStack();
		minStack.push(-2);
		minStack.push(0);
		minStack.push(-3);
		minStack.min();  
		minStack.pop();
		minStack.top();
		minStack.min(); 
		System.out.print(minStack.min());
	}

}

/**
 * 最小栈问题，主栈和辅助栈同步更新
 */
class MinStack {
	Deque<Integer> stack1;
	Deque<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
    	stack1 = new LinkedList<Integer>();
		stack2 = new LinkedList<Integer>();
    }
    
    public void push(int x) {
    	stack1.push(x);
    	if(stack2.isEmpty()||stack2.peek()<x) {
    		stack2.push(x);
    	}else {
    		stack2.push(stack2.peek());
    	}
    }
    
    public void pop() {
    	stack1.pop();
    	stack2.pop();
    }
    
    public int top() {
    	return stack1.peek();
    }
    
    public int min() {
    	return stack2.peek();
    }
}